package String_process;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/13 16:36
 * @description:  给定一个可包含重复数字的序列nums，按任意顺序 返回所有不重复的全排列。
 */
public class Permutation2 {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        String []arr = sr.nextLine().split(" ");
        int [] nums = new int[arr.length];
        for(int i = 0; i<arr.length;i++){
            nums[i] = Integer.parseInt(arr[i]);
        }
        Arrays.sort(nums);
        System.out.println(new Permutation2_solution().permuteUnique(nums));
    }
}

class Permutation2_solution{
    List<List<Integer>> res = new ArrayList<>();
    boolean vis[];
    public List<List<Integer>> permuteUnique(int [] nums){
        List<Integer> trace = new ArrayList<>();
        vis = new boolean[nums.length];
        int ids = 0;
        dfs(nums,vis,trace,ids);
        return res;
    }
    public void dfs(int []nums,boolean []vis,List<Integer> trace,int ids){
        if(trace.size() == nums.length){
            res.add(new ArrayList<>(trace));
            return;
        }
        //for循环保证了从数组中从前往后一个一个取值，再用if判断条件,所以nums[i-1]一定比nums[i]先被取值和判断
        //每递归一层都是在寻找数组对应递归深度位置的值，每一层用for循环来寻找
        for(int i = 0;i < nums.length; i++){
             //如果nums[i-1]被取值了，那vis[i-1]会被置1，只有递归再回退到这一层时再将它置0
            //当vis[i-1]==1时，说明nums[i-1]和nums[i]分别属于两层递归中，也就是我们要用这两个数分别放在数组的两个位置，这时不需要去重
            //但是当vis[i-1] == 0时，说明nums[i-1]和nums[i]属于同一层递归中(只是for循环进入了下一层循环)，也就是要用这两个数放在数组中的同一个位置上，要去重
            //所以用vis[i-1] 可以判断是否是当前层次，当==0时，说明是同层，否则是不同层
            if(vis[i] || ( i>0 && nums[i] == nums[i-1] && !vis[i-1])){
                continue;
            }
            //做选择
            trace.add(nums[i]);
            vis[i] = true;
            //下一层 回溯
            dfs(nums,vis,trace,ids+1);  //ids表示深度，for循环的i代表某深度下的层次
            //取消选择
            vis[i] = false;
            trace.remove(ids);
        }
    }
}